package leetcode_core.leetcode_1;

import java.util.HashMap;
import java.util.Map;

public class SubarraySum {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        //map:前缀和->该前缀和出现的次数
        Map<Integer,Integer> map = new HashMap<>();
        //base-case
        map.put(0,1);//前0项的和为0,而且出现了一次
        int ans = 0,sum0_i = 0;
        for(int i =0;i<n;i++){
            sum0_i += nums[i];
            //这是我们想找的前缀和nums[0....j]
            int sum0_j = sum0_i-k;
            //如果前面有这个前缀和,那么直接更新答案
            if(map.containsKey(sum0_j)){
                ans += map.get(sum0_j);
            }
            //把前缀和nums[0....i]加入并记录出现次数
            map.put(sum0_i,map.getOrDefault(sum0_i,0)+1);
        }
        return ans;
    }
}
